#include<iostream>
using namespace std;
int data[]={5,7,0,3,4,1,6,5};
void insert_sort()
{
	for(int i=1;i<8;i++)
	{
		int key=data[i];
		int j=i-1;
		while(j>=0 && data[j]<key){
			data[j+1]=data[j];
			j--;
		}
		data[j+1]=key;
		
	}
}

void swap(int &x, int &y)
{
	int tmp=y;
	y=x;
	x=tmp;
}

int partition(int l, int r)
{
	int pivot=data[l];
		int i=l-1;
		int j=r+1;
	while(true)
	{	
		
		do 
			i++;
		while(data[i]<pivot);

		do 
			j--;
		while(data[j]>pivot);
	
		if(i<j)
			swap(data[i],data[j]);
		else
			return j;
	}
}

void quick_sort(int l,int r)
{
	if(l<r)
	{
		int p=partition(l,r);
		quick_sort(l,p);
		quick_sort(p+1,r);
	}
}



void quickSort(int left, int right)
{
	if(left>=right)
		return;
	//partition
	int pivot=data[left];
	int l=left;
	int r=right;
	while(true){
		//not <=, or l may go straight to the right and get out of bound
		while(data[l]<pivot)
			l++;
		while(data[r]>pivot)
			r--;
		if(l>=r)
			break;
		int tmp=data[l];
		data[l]=data[r];
		data[r]=tmp;
		//necessary, otherwise may get trapped in the while loop when data[l]=data[r]=pivot
		l++;
		r--;		
	}
	//recursion
	if(left<r)
		quickSort(left,r);
	if(r+1<right)
		quickSort(r+1,right);
}





int main()
{
	quickSort(0,7);
	for(int i=0;i<8;i++)
		cout<<data[i];
	cout<<endl;
}
